Network protocols, such as the Internet Protocol (IP), are designed to facilitate communication between network devices through an open exchange of data. However, standard IP and other similar protocols were not designed for, and do not provide, network security. As a result, network devices are susceptible to malicious attacks perpetrated through the network including theft of data, denial of service attacks, the proliferation of computer viruses, and the like.
A firewall is a tool used to protect individual users, network devices, and networks in general, from malicious attacks, while also adding the ability to control the exchange of data over the network through implementation of a policy. The firewall implements the policy by examining network packets and determining, based on the examination, whether the packets should be permitted, or conversely blocked, from further traversing the network. Other functions including intrusion detection, virus protection, and parental controls are also implemented through the firewall.
A component of the firewall is a set of filters. A filter is a data structure that includes filter conditions and actions. The filter conditions are used to identify packets that are subject to the actions specified in the filter. Examples of filter conditions include hardware addresses, e.g. media access control (MAC) addresses, network addresses, e.g. Internet protocol (IP) addresses, protocol type, e.g. transport control protocol (TCP), and port numbers. Examples of actions specified in a filter include permit, i.e. allow the packet to continue to traverse the network and block, i.e. preclude the packet from further network traversal.
The filters are organized in an index. When a packet is sent from, or received by, a network device, the firewall traverses the index to identify any “matching” filters. The firewall identifies matching filters by comparing information in the packets, e.g. IP addresses, ports, and/or protocol, to corresponding filters conditions in one or more of the filters. If the packet information satisfies all filter conditions in a filter, the filter matches the packet. After the firewall identifies any matching filters, the network device determines whether to take any actions specified in the matching filters.
When the types of filter conditions designated in the filters are static and predictable, the type of index used, and organization thereof, can be pre-selected for the filters. Some firewalls, however, permit generic filters to be used wherein the filter conditions are extensible and dynamically change depending on system need. Accordingly, it is not possible to pre-select an optimal index type and index organization. Moreover, a single type of index may not be suitable for indexing all filters.